//
// Created by Administrator on 2022/10/22.
//

//使用栈实现四则运算
//1.将输入的中缀表达式利用栈输出为后缀表达式
//2.对输出的后缀表达式利用栈计算出结果

//这里使用链栈来实现
#include <stdio.h>
#include <malloc.h>

#define ERROR 0
#define OK 1
typedef char ElementType;
typedef int Status;
//声明链栈节点
typedef struct LinkStackNode{
    ElementType data;
    struct LinkStackNode* next;
}LinkStackNode,*LinkStackPtr;
//声明链栈
typedef struct {
    LinkStackPtr top;
    int count;
}LinkStack;

//初始化一个链栈
void initLinkStack(LinkStack* linkStack){
    (*linkStack).top=NULL;
    (*linkStack).count=0;
}
//向栈中压入一个元素
Status push(LinkStack* stack,ElementType e){
    LinkStackPtr p=(LinkStackPtr)malloc(sizeof(struct LinkStackNode));
    p->data = e;
    p->next = stack->top;
    stack->top = p;
    stack->count++;
    return OK;
}
//出栈一个元素
Status pop(LinkStack* stack,ElementType* e){
    if(stack->count==0){
        return ERROR; //栈为空
    }
    *e = stack->top->data;
    LinkStackPtr p =stack->top;
    stack->top=p->next;
    free(p);
    stack->count--;
    return OK;
}

void main(){
    //初始化栈
    LinkStack stack;
    initLinkStack(&stack);

    //将输入的中缀表达式存储到一个数组中
    char exp[30] ;
    char exp2[30];
    scanf("%s",exp);
    int index2;
    char tmp;


    //读取数组中的表达式,将中缀表达式转换为后缀表达式
    //+ 43
    //- 45
    //* 42
    // / 47
    // ( 40
    // ) 41
    for (int i = 0; i < 30; ++i) {
        if(exp[i]!='\0'){

            //如果字符串是数字,将它存储到另一个数组中
            if(exp[i]>=48&&exp[i]<=57){
                exp2[index2++] = exp[i];
            }else{
                //如果栈为空或者为左括号 就入栈
                if(stack.top||exp[i]==40){
                    push(&stack,exp[i]);
                }else if(exp[i]==41){ //如果是右括号 就要出栈直至匹配到左括号

                    while(1) {
                        pop(&stack, &tmp);
                        if(tmp==40){
                            break;
                        }
                        exp2[index2++] = tmp;
                    }
                    //如果是乘除优先级高于栈顶元素,就先将优先级高的放入,再出栈一个放入
                }else if((stack.top->data==43||stack.top->data==45)&&(exp[i]==42||exp[i]==47)){
                    exp2[index2++] =exp[i];
                    pop(&stack,&tmp);
                    exp2[index2++] = tmp;
                }else{ //如果是其他情况,就直接放入
                    exp2[index2++] =exp[i];
                }
            }
            continue;
        }
        break;
    }
    //最后将后缀表达式计算出结果
    for (int i = 0; i < 30; ++i) {
        printf("%c\n",exp2[i]);
    }

}

